package offer;
/**
 * @author SSK
 * //把数组排成最小的数
 */
public class T33 {
    public String PrintMinNumber(int [] numbers) {
        if(numbers==null) {
            return null;
        }
        String strings[][] = new String[2][numbers.length];
        strings[0] = new String[numbers.length];
        strings[1] = new String[numbers.length];
        for (int i = 0; i < numbers.length; i++) {
            strings[0][i] = numbers[i] + "";
        }
        int cur = 0;
        for (int i = 1; i < numbers.length; ) {
            i<<=1;
            for (int j = 0; j < numbers.length; j+=i) {
                 int right = Math.min(j+i/2,numbers.length-1);
                 int left = j;
                 int lend = right;
                 int rend = Math.min(j+i,numbers.length);
                 int cnt = 0;
                 while (left < lend && right < rend) {
                     if ((strings[cur][left] + strings[cur][right]).compareTo(strings[cur][right] + strings[cur][left]) < 0) {
                          strings[cur^1][j+cnt] = strings[cur][left];
                          cnt++;
                          left++;
                     }else {
                         strings[cur^1][j+cnt] = strings[cur][right];
                         cnt++;
                         right++;
                     }
                 }
                 while (left < lend) {
                     strings[cur^1][j+cnt] = strings[cur][left];
                     cnt++;
                     left++;
                 }
                 while (right < rend) {
                     strings[cur^1][j+cnt] = strings[cur][right];
                     cnt++;
                     right++;
                 }
            }
            cur^=1;
        }
        String minNumber = "";
        for (String str: strings[cur]) {
            minNumber+=str;
        }
        return minNumber;
    }

    public static void main(String[] args) {
        System.out.println(new T33().PrintMinNumber(new int[]{3,32,321}));
    }
}
